n=5000;
m=100;
w=[45,67,67,31,71,44,92,18,42,20,57,33,23,58,77,17,18,15,75,50,74,56,60,41,18,53,88,17,29,41,38,76,68,78,17,11,6,87,21,56,21,25,27,38,51,71,78,46,19,78,14,5,93,95,34,94,4,70,28,90,86,3,71,73,93,78,80,6,24,1,65,82,55,13,96,41,32,97,99,21,18,57,8,100,19,81,86,91,16,34,68,72,88,53,90,40,43,28,38,73,16,100,64,40,48,71,21,65,16,10,68,87,49,2,47,53,47,40,61,61,56,5,92,36,73,63,4,26,2,89,56,28,54,57,29,51,65,60,81,30,1,6,55,59,53,91,79,14,29,85,7,79,91,7,75,17,31,21,8,86,25,28,65,17,29,28,49,10,68,45,13,53,1,3,1,1,63,41,78,58,93,52,83,33,17,7,82,43,1,2,96,57,66,16,11,78,11,57,16,93,59,56,45,41,14,3,25,22,81,76,1,58,51,60,85,20,98,39,36,71,2,3,4,50,73,88,38,82,23,39,33,89,32,61,60,66,83,64,48,73,41,84,6,9,35,51,87,18,98,73,50,20,72,9,46,93,64,89,43,90,65,28,8,29,17,2,35,61,4,24,5,18,10,93,37,7,85,47,66,13,9,82,27,70,30,17,3,86,52,31,50,60,58,90,90,57,41,86,1,84,85,47,66,34,83,66,26,40,29,65,9,73,96,78,64,93,44,86,6,14,21,30,70,79,68,82,3,94,95,24,15,62,86,83,43,40,94,36,63,25,43,69,10,73,13,72,45,62,62,91,16,68,83,34,75,60,44,80,78,75,9,97,24,8,47,67,57,68,38,7,3,5,83,47,37,37,89,50,45,40,84,59,44,85,51,34,59,45,86,47,52,8,6,93,33,68,60,18,36,63,43,19,80,88,58,34,63,65,13,62,65,20,90,39,68,47,3,87,40,5,7,65,36,85,74,95,37,81,29,45,47,43,37,48,27,43,86,91,72,2,75,65,60,53,80,99,44,16,81,53,26,36,5,68,19,39,5,65,89,16,10,44,99,79,12,37,31,29,9,99,87,71,65,51,47,91,31,59,1,64,95,32,18,35,26,45,24,49,19,61,65,35,39,27,39,44,96,39,68,38,77,51,37,40,1,84,29,42,37,27,43,5,55,56,39,21,28,72,88,8,36,48,64,96,69,29,60,64,77,70,44,23,28,2,25,22,73,27,3,79,75,62,77,37,99,60,2,10,25,76,83,47,76,26,11,19,34,3,58,70,79,86,17,63,44,91,32,8,32,50,20,33,74,13,56,31,1,22,15,47,39,39,24,82,92,31,21,82,19,26,68,10,58,47,35,66,95,5,41,66,93,91,94,68,72,13,71,40,32,48,69,3,48,27,68,69,98,71,99,95,89,20,38,5,3,45,7,37,96,57,45,44,42,91,54,37,95,15,19,59,64,19,53,14,7,61,78,81,47,53,76,62,94,65,86,26,32,79,65,39,43,11,12,35,62,62,62,59,49,58,75,28,65,18,42,72,24,17,55,29,52,26,37,45,96,99,5,49,99,50,96,96,52,51,81,42,1,83,98,46,56,37,84,100,71,31,37,70,51,19,46,41,95,70,94,6,10,36,94,3,54,62,80,32,51,81,1,46,3,8,69,39,19,63,34,37,82,80,30,59,60,82,68,54,22,73,14,65,96,18,62,87,83,91,86,28,52,88,59,6,84,55,72,5,57,1,84,49,66,58,68,84,71,39,13,15,11,22,90,72,65,3,24,17,32,44,10,95,83,85,84,94,20,49,27,40,8,71,71,56,87,93,23,88,52,11,80,20,8,11,69,37,79,3,66,86,19,3,68,38,20,100,47,26,24,82,77,4,23,45,38,89,77,17,28,71,19,68,78,6,88,98,27,31,45,84,20,29,23,18,67,56,55,49,25,63,2,85,26,82,66,14,66,56,1,98,67,65,8,70,50,55,27,52,26,91,55,97,55,62,24,10,75,77,60,36,33,44,31,92,99,89,21,92,46,13,85,39,51,63,100,31,21,98,1,73,56,7,49,81,15,78,34,99,81,57,96,80,100,85,20,37,80,66,52,73,43,25,90,17,17,84,57,81,18,72,82,97,25,74,15,93,51,16,29,12,65,49,65,27,22,15,71,61,76,52,39,78,61,35,13,76,89,76,60,74,10,95,10,99,38,5,58,77,56,24,53,47,98,64,88,3,6,41,94,72,16,11,79,11,11,67,44,64,49,84,6,80,8,62,21,25,55,50,32,33,61,30,82,34,41,42,70,57,33,79,23,50,23,3,82,27,81,86,9,29,40,43,6,91,61,82,55,53,91,48,6,8,39,75,24,42,13,20,30,56,54,62,64,10,10,17,9,40,64,71,31,58,24,89,19,21,61,5,80,68,23,67,33,7,38,42,83,11,23,93,99,90,34,61,52,70,45,36,37,44,28,78,65,45,22,15,87,96,39,29,64,21,46,72,11,23,45,91,67,81,6,53,99,65,72,96,18,52,23,36,88,24,81,76,1,80,81,76,37,38,68,62,75,6,85,22,58,30,88,99,81,31,51,20,93,43,13,32,100,81,60,58,40,84,1,7,94,92,2,56,72,49,27,55,46,13,83,69,4,24,5,81,59,42,74,43,97,70,73,44,61,16,66,37,11,12,83,34,28,48,12,100,86,86,37,8,75,71,13,62,31,23,1,70,38,99,78,30,6,46,7,84,1,91,70,33,11,51,85,54,55,86,96,82,14,60,57,29,60,48,35,44,1,29,31,36,87,88,27,51,34,61,16,52,48,72,99,3,59,98,15,17,95,76,93,37,44,1,24,7,95,12,100,19,28,32,48,69,73,33,75,8,44,85,3,89,66,65,63,34,23,2,15,46,28,95,36,94,12,59,46,37,46,3,48,20,71,6,87,32,27,96,31,24,13,12,49,18,83,40,66,38,90,64,70,13,6,87,49,11,38,3,38,67,72,60,49,5,6,47,18,34,83,39,30,23,31,56,37,72,28,10,37,55,94,7,74,99,42,68,43,7,55,89,24,81,100,97,56,33,61,5,21,62,4,63,98,22,43,82,64,93,23,86,96,58,86,6,59,95,14,22,23,30,45,61,2,16,88,28,52,53,8,79,17,80,17,72,15,64,37,41,30,71,29,86,82,74,30,56,33,74,3,72,48,21,41,47,9,15,95,37,7,75,71,60,98,33,20,70,22,58,90,75,42,74,3,96,63,32,74,70,7,82,54,8,71,51,23,62,24,67,45,14,81,74,90,53,99,8,40,69,15,34,88,74,16,44,35,5,97,51,51,52,5,49,77,56,67,53,56,75,32,7,58,14,63,18,85,22,29,5,69,44,17,58,36,51,9,7,47,73,97,79,35,22,56,15,14,16,37,49,18,74,28,47,58,100,61,68,29,47,3,100,67,49,37,54,87,70,85,99,25,28,2,92,59,20,96,58,39,54,37,65,3,3,78,43,65,33,74,83,4,27,46,18,59,66,46,4,12,83,79,62,59,1,42,99,64,73,68,44,94,41,46,48,22,54,23,32,31,17,62,16,79,83,54,26,99,52,1,26,58,93,4,22,64,29,33,95,76,63,89,45,86,16,36,11,34,42,10,25,41,52,39,77,7,24,30,69,44,62,53,92,63,94,80,50,59,17,56,76,4,88,50,11,51,56,72,57,13,100,63,51,45,45,43,12,86,8,86,1,14,62,11,4,74,28,30,91,62,39,43,67,73,68,84,72,92,9,70,22,82,53,12,40,28,74,70,89,98,15,76,60,98,14,71,96,22,60,54,4,88,71,85,15,54,13,62,35,83,55,42,67,49,70,58,46,3,85,9,6,5,79,57,94,14,19,56,59,89,6,61,93,85,31,99,68,2,78,33,21,55,81,86,15,34,14,16,25,52,91,67,89,89,18,32,89,80,17,10,14,38,69,99,39,1,33,24,99,23,78,49,56,12,76,29,50,9,64,100,47,89,48,50,61,13,6,6,19,46,12,39,44,45,7,23,68,12,35,21,43,36,78,37,19,19,1,85,20,58,19,70,62,57,75,79,3,85,33,62,96,62,16,100,25,38,30,26,86,66,23,13,28,9,30,2,27,42,82,58,98,17,68,27,98,67,34,40,58,65,79,22,46,43,8,48,29,30,99,47,9,40,93,45,82,94,74,83,46,10,83,50,55,38,15,43,57,33,83,37,34,97,78,14,39,100,73,21,57,7,66,63,96,76,7,85,22,23,33,97,19,23,10,74,88,85,20,65,57,26,23,2,28,5,13,75,90,51,63,87,36,14,98,58,19,47,100,56,63,12,21,35,66,42,97,81,87,43,62,82,61,90,86,21,70,61,87,17,28,71,2,35,54,7,85,23,30,98,39,79,82,93,100,94,88,93,54,100,74,74,7,21,6,97,80,41,18,89,61,55,88,72,82,45,32,91,1,22,58,99,65,57,81,46,23,14,60,5,91,62,65,59,5,19,11,87,76,96,88,93,79,18,54,30,98,88,81,52,43,65,74,56,86,91,27,67,94,38,70,71,89,13,66,27,29,52,36,64,19,14,59,93,37,69,54,53,83,25,73,96,59,61,30,7,82,100,45,32,4,86,55,14,31,93,19,20,39,71,57,100,57,45,39,26,86,81,93,49,73,43,13,41,49,69,23,22,68,97,57,38,63,51,90,25,39,35,56,68,43,32,59,63,6,62,64,42,31,70,90,27,72,83,64,21,69,79,60,36,61,86,46,91,69,69,31,62,35,59,35,46,40,36,37,21,86,32,31,74,29,55,38,21,24,12,82,55,26,63,93,49,54,26,56,53,3,79,15,12,12,44,82,77,15,87,35,43,21,40,31,75,54,64,11,40,4,55,88,39,81,94,86,96,64,1,96,94,5,66,53,27,2,59,12,3,72,64,38,59,70,37,52,7,38,67,63,53,62,92,97,88,14,91,16,43,26,88,29,40,95,82,69,63,1,63,38,79,67,56,9,70,62,57,75,20,31,73,22,26,16,62,17,36,93,44,34,21,35,83,87,61,84,26,31,4,48,9,99,45,12,55,61,41,97,60,75,41,67,33,94,65,51,62,20,26,37,50,41,26,58,9,59,11,1,34,88,34,81,68,63,85,2,64,76,66,11,99,24,50,72,36,1,68,27,11,39,54,88,15,44,54,32,15,95,29,95,19,31,37,74,9,94,71,55,23,24,7,8,82,22,6,84,17,7,1,35,18,33,64,4,51,99,70,97,37,46,31,36,97,29,93,8,20,49,55,73,17,12,95,31,8,94,55,67,10,86,62,9,86,23,49,98,78,70,96,33,34,49,85,44,95,96,86,31,12,15,69,45,2,97,86,57,34,31,20,71,63,60,17,79,72,28,83,70,55,70,93,16,94,42,75,29,78,94,29,26,58,5,66,15,41,46,7,70,7,50,45,63,97,60,93,82,59,24,91,72,18,54,21,65,58,24,33,17,22,59,64,83,49,94,40,10,7,67,16,54,64,94,50,98,72,63,86,26,88,51,13,43,8,22,37,98,26,52,7,93,6,74,40,92,74,86,76,16,43,21,72,61,69,71,11,49,55,56,24,18,87,10,6,8,73,87,63,5,89,12,93,89,18,31,98,82,72,13,3,31,70,70,27,18,5,13,13,80,23,39,99,72,11,64,4,80,36,36,89,79,28,23,71,93,87,38,48,49,76,36,31,44,47,97,5,51,16,53,94,71,23,24,3,70,5,69,97,57,62,73,1,47,14,58,70,13,17,75,32,60,46,6,90,99,7,91,26,90,3,14,39,53,12,100,96,65,4,46,19,55,54,43,21,43,44,91,32,76,51,7,57,53,93,43,90,87,94,54,43,4,90,80,85,83,54,66,98,77,69,6,88,16,89,37,32,1,2,21,50,96,38,38,62,34,21,55,89,26,19,65,38,60,24,32,14,2,88,3,34,66,47,57,39,26,54,91,54,26,67,76,1,71,5,86,85,80,96,83,30,14,7,84,32,100,46,13,60,68,22,65,90,91,15,72,19,34,74,86,2,94,4,45,39,89,49,49,97,71,99,27,69,8,53,80,73,66,84,59,69,93,45,22,19,53,69,45,94,100,17,80,26,49,40,11,38,24,9,98,2,23,45,81,78,12,62,100,78,40,57,35,75,79,49,54,42,85,32,39,11,44,54,76,73,71,55,54,89,3,66,22,100,87,64,3,12,22,9,36,25,68,77,100,88,12,33,51,9,56,49,71,66,34,1,23,91,11,59,15,91,1,40,80,27,89,48,44,9,17,47,61,28,2,13,42,38,30,6,51,6,77,23,59,71,61,48,47,60,90,78,60,2,87,26,84,15,83,14,85,88,31,36,54,34,100,89,78,4,59,48,34,80,23,83,14,86,34,88,87,57,64,100,56,89,81,25,86,96,2,66,64,86,82,7,11,18,52,20,83,10,43,50,90,78,41,44,5,87,17,60,23,60,29,70,24,36,19,12,51,35,42,67,20,17,79,100,37,26,56,15,29,100,84,4,25,50,80,83,34,35,26,6,84,10,13,24,18,43,92,4,54,62,38,37,14,50,77,97,47,65,6,69,84,30,65,83,54,75,28,99,95,68,29,10,77,83,83,53,53,26,82,92,51,6,96,22,8,65,58,83,69,11,39,71,45,8,89,31,38,65,41,13,44,43,49,97,51,88,41,41,38,81,51,73,7,96,22,56,53,63,88,57,43,36,58,33,31,22,17,31,12,96,11,9,100,33,28,67,32,95,61,62,75,92,84,51,97,22,29,31,65,86,85,85,54,80,41,90,31,12,93,44,28,44,1,86,7,24,28,59,30,46,84,45,98,51,53,73,13,14,29,96,21,100,19,79,29,15,94,34,20,31,13,65,78,53,77,77,73,90,30,86,29,43,89,49,67,39,13,23,20,62,73,26,92,47,82,88,77,77,66,50,42,45,28,71,71,31,73,97,66,45,69,35,91,56,26,16,69,14,78,30,29,56,83,50,10,21,20,4,49,2,41,46,97,43,75,74,22,82,29,59,51,59,67,3,90,56,13,82,88,85,42,94,64,19,81,92,36,32,31,58,41,26,39,85,50,58,79,61,60,46,19,27,52,51,30,21,13,7,71,44,100,81,90,22,94,38,60,27,61,38,65,23,29,50,15,24,60,36,82,28,59,96,22,91,55,16,88,70,57,12,92,50,14,72,58,31,62,3,84,28,65,78,60,10,66,72,99,43,79,47,80,76,37,66,85,2,42,72,19,30,29,69,4,75,61,48,2,9,60,65,85,18,96,44,5,8,15,57,49,77,56,1,59,17,58,62,93,30,88,82,23,92,17,9,71,52,5,16,33,19,56,44,67,18,95,4,11,44,52,38,34,54,33,64,17,66,29,14,34,4,66,58,58,21,53,64,60,36,2,95,44,97,99,56,33,100,93,14,76,19,66,10,22,59,49,47,48,80,1,60,64,79,39,96,26,88,46,62,8,8,5,23,56,24,12,53,60,63,91,10,14,8,88,100,84,100,69,10,58,59,41,62,78,96,67,40,89,74,51,32,23,3,94,51,99,16,100,16,28,95,76,76,98,97,62,6,98,44,87,97,75,74,90,22,38,90,74,82,25,62,1,32,49,86,7,47,97,32,42,91,17,77,36,80,48,71,9,87,74,80,58,100,49,69,2,35,78,22,9,31,35,49,39,91,98,73,50,27,92,73,66,59,78,13,83,6,8,96,28,66,93,23,67,59,51,33,8,65,3,72,83,77,70,34,21,33,53,7,54,91,46,79,76,100,1,30,62,19,6,12,99,69,75,42,57,66,64,94,85,40,49,47,37,61,4,59,79,83,67,21,44,19,40,96,53,59,76,13,8,33,25,94,42,55,72,100,36,25,65,51,56,19,95,75,69,40,27,73,62,95,97,6,38,75,42,47,60,78,64,38,53,78,66,31,62,44,43,82,4,24,50,13,17,33,19,81,77,80,20,66,89,27,68,75,22,72,72,94,65,67,29,3,58,64,85,15,34,92,81,100,58,35,31,63,17,3,3,73,85,7,79,34,64,97,75,67,72,4,6,6,89,69,39,67,10,89,90,45,83,51,19,85,21,11,75,58,74,54,32,22,11,51,56,80,32,95,85,11,91,48,3,26,59,87,97,76,57,95,77,97,11,10,87,62,81,50,71,94,90,78,30,53,1,34,22,85,51,4,65,27,79,65,77,39,79,31,76,3,12,8,57,53,33,51,57,46,15,5,92,42,13,95,21,50,66,23,3,33,24,76,20,58,64,61,62,36,1,4,52,7,14,35,68,66,38,59,35,10,2,9,64,14,30,94,64,52,39,97,41,15,64,26,26,4,71,94,42,14,90,78,41,9,27,99,28,35,64,19,31,81,42,8,67,95,77,61,61,91,87,90,1,31,97,40,27,58,47,70,95,48,17,89,23,52,84,10,77,29,90,9,58,48,68,36,67,45,66,49,10,24,2,49,35,90,58,97,2,36,72,79,76,83,3,37,18,37,39,19,45,27,76,78,64,23,39,4,18,31,58,11,84,95,37,70,42,40,32,77,5,41,54,92,32,75,43,58,81,55,11,98,11,11,95,75,69,37,43,8,58,94,52,61,54,75,42,97,84,68,42,60,54,6,94,24,64,15,81,52,73,55,45,99,6,41,58,43,29,51,29,91,13,82,64,17,66,57,28,58,99,71,28,59,74,83,24,17,56,40,1,51,54,9,51,58,19,18,29,25,35,12,76,15,27,82,86,94,34,24,64,29,20,84,70,48,25,51,98,18,80,25,36,19,56,12,96,60,54,14,44,67,48,29,52,87,2,58,55,72,40,21,20,70,63,84,65,72,3,10,38,27,27,87,29,52,15,53,12,35,7,76,88,44,68,65,61,31,21,47,87,62,38,12,55,54,95,23,84,71,75,21,91,28,11,49,33,47,34,75,24,100,85,25,89,96,95,41,96,23,87,93,40,78,16,52,25,3,74,92,43,22,10,68,33,17,94,76,14,98,22,15,19,88,26,24,17,31,1,36,48,83,61,79,20,31,36,89,51,90,6,23,39,95,48,22,1,42,29,39,82,99,23,28,45,9,44,42,26,21,94,51,34,84,19,66,10,29,25,60,8,72,88,90,11,64,65,16,94,100,20,84,61,8,17,67,79,92,12,55,43,38,81,14,100,44,25,17,71,16,82,61,72,47,36,38,11,31,73,38,5,33,90,96,49,51,24,4,60,18,90,46,9,18,47,8,20,100,98,73,41,33,76,11,12,73,82,90,100,2,20,98,88,70,85,69,92,18,27,70,84,78,22,7,42,65,40,6,66,5,39,82,38,18,47,51,23,13,50,3,21,44,57,35,62,20,99,71,45,99,51,53,16,47,3,35,40,79,80,75,97,57,9,31,26,44,34,49,65,54,11,52,58,93,41,43,68,73,85,41,77,49,25,98,43,19,54,6,43,97,90,68,41,42,14,80,76,15,51,96,91,94,62,7,76,81,96,71,48,39,11,64,67,88,75,9,81,33,11,95,5,81,32,100,50,54,18,66,72,36,12,4,80,80,83,88,49,39,82,26,100,4,1,28,39,36,1,46,43,45,98,59,56,1,32,40,72,11,7,33,46,9,66,14,44,44,74,84,100,1,98,77,23,10,98,28,62,77,9,55,4,59,91,89,40,83,59,16,84,7,79,96,39,68,37,22,19,66,54,27,90,30,46,43,70,44,63,36,14,31,1,51,96,63,21,90,43,93,13,79,26,88,28,12,70,47,13,79,38,38,33,56,33,23,60,73,63,74,81,97,57,78,86,60,15,93,6,2,31,25,33,37,92,49,60,49,35,12,90,98,60,40,33,48,80,38,49,70,13,19,86,95,59,70,12,6,22,33,12,40,48,9,97,24,80,98,35,42,79,94,95,46,42,64,71,59,31,72,57,95,97,81,66,21,35,19,59,39,68,87,32,97,80,36,79,61,45,63,7,71,52,24,65,80,98,86,43,11,31,17,95,68,82,43,31,44,77,74,79,56,34,35,74,68,97,97,64,99,68,16,75,25,57,100,100,84,43,63,5,11,35,98,17,96,32,37,7,4,89,45,59,24,26,10,65,58,74,54,68,4,64,81,26,96,67,81,76,29,46,1,92,97,44,5,37,47,75,11,79,79,88,45,92,24,18,26,91,78,36,62,46,8,37,98,69,51,40,95,33,47,45,21,66,86,68,95,48,11,64,62,11,28,1,51,70,67,74,80,50,17,82,9,24,96,87,55,32,67,39,70,18,92,99,64,69,65,65,57,42,2,46,36,27,77,100,69,93,19,52,85,67,98,24,51,92,44,15,21,63,59,9,30,12,41,68,80,2,66,71,46,47,92,34,26,99,63,34,45,93,68,42,99,14,22,54,76,51,19,40,82,93,84,40,67,3,65,69,75,48,95,28,45,94,10,62,45,22,61,98,18,73,31,60,4,54,33,73,1,33,78,50,75,79,6,67,70,11,53,49,64,81,26,98,44,89,75,68,51,42,24,32,92,75,12,48,87,37,42,96,12,42,4,26,81,62,60,99,61,28,60,16,46,55,79,80,58,98,64,76,17,61,75,89,6,41,38,48,59,93,74,12,26,50,34,75,34,32,94,30,61,50,56,74,7,83,15,91,71,34,45,44,72,95,15,27,66,52,30,91,10,11,24,91,28,100,99,1,84,69,25,91,59,72,73,20,10,29,66,54,98,5,9,54,51,22,47,25,7,55,31,74,79,99,29,83,64,73,84,69,25,43,13,30,37,63,100,81,3,9,39,41,89,26,5,22,77,33,52,32,65,72,74,20,54,49,100,12,16,17,69,38,39,36,93,40,16,63,17,78,14,95,82,64,23,83,72,50,88,39,18,46,40,57,50,81,39,76,90,80,62,84,21,96,21,90,70,20,81,76,59,58,55,74,17,52,81,94,7,44,3,73,4,74,32,35,77,1,54,46,55,73,16,98,96,92,15,63,28,54,11,13,55,33,54,91,5,8,37,84,97,31,26,55,15,4,5,70,56,25,67,45,62,51,88,14,48,37,13,99,86,67,89,56,88,39,87,42,85,17,72,13,87,4,5,57,90,69,28,94,21,52,62,46,51,48,24,97,78,3,58,32,76,61,29,87,99,13,46,43,99,70,94,76,45,14,75,2,46,8,59,39,24,15,40,8,72,18,63,11,21,22,77,13,99,87,78,59,56,14,72,30,31,7,12,43,30,77,87,72,42,78,63,12,8,36,47,77,74,20];